package cn.zhaoyuening.algorithms.dynamic;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by Buynow on 2017/8/15.
 */
public class MaxIncreaseSeq {

    public static void helper(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = 1;
        int curNum = 0;
        int tmpVal = 0;
        for (int i=1;i<arr.length;i++) {
            curNum = arr[i];
            tmpVal = dp[i-1];
            for (int j=i;j>=0;j--) {
                if (curNum > arr[j]) {
                    tmpVal = Math.max(tmpVal, dp[j] + 1);
                    break;
                }
            }
            dp[i] = tmpVal;
        }
        System.out.println(dp[arr.length-1]);
    }


    public static void helper2(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = 1;
        int curNum = 0;
        int tmpVal = 0;
        for (int i=1;i<arr.length;i++) {
            curNum = arr[i];
            tmpVal = 1;
            for (int j=i;j>=0;j--) {
                if (curNum > arr[j]) {
                    tmpVal = Math.max(tmpVal, dp[j] + 1);
                    break;
                }
            }
            dp[i] = tmpVal;
        }

        int maxIndex = 0;
        for (int i=1;i<dp.length;i++) {
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        int[] seqArr = new int[dp[maxIndex]];
        int nextOrder = dp[maxIndex]-1;
        seqArr[seqArr.length - 1] = arr[maxIndex];
        for (int i=maxIndex-1;i>=0;i--) {
            if (dp[i] == nextOrder) {
                nextOrder--;
                seqArr[dp[i] - 1] = arr[i];
            }
        }

        

        System.out.println(Arrays.toString(seqArr));
    }
    public static void main(String[] args) {
        helper2(new int[]{2,1,5,3,6,4,8,9,7});
    }
}
